/**
 * Created with IntelliJ IDEA.
 * Description :
 * User: $ {USER}
 * Date: $ {YEAR}-$ {MONTH}一$ { DAY}
 * Time: ${ TIME}
 */
/**
 * 题目：前序遍历和中序遍历创建二叉树
 * 思路：通过前序遍历找到根结点，再通过根结点在中序遍历中找到左子树和右子树，递归创建即可
 */


public class Test {
    // 创建一棵二叉树，先创建根结点，再创建左子树和右子树
    // 根结点就是根据前序遍历来找，
    // 左子树和右子树都是根据前序遍历和中序遍历来找出左子树和右子树的根结点
    private int rootIndex;
    public TreeNode buildTree(int[] preorder, int[] inorder) {

        return buildTreeChild(preorder, inorder, 0, inorder.length-1);
    }

    private TreeNode buildTreeChild(int[] preorder, int[] inorder,
                                    int inorderbegin, int inorderend) {
        // 空树
        if (inorderbegin > inorderend) {
            return null;
        }
        // 创建根结点
        TreeNode root = new TreeNode(preorder[rootIndex]);
        // 找到边界
        int border = findVal(inorder, preorder[rootIndex]);
        rootIndex++;
        // 创建左子树
        root.left = buildTreeChild(preorder, inorder, inorderbegin, border-1);
        // 创建右子树
        root.right = buildTreeChild(preorder, inorder, border+1, inorderend);
        return root;
    }

    private int findVal(int[] inorder, int val) {
        for (int i = 0; i < inorder.length; i++) {
            if (inorder[i] == val) {
                return i;
            }
        }
        return -1;
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}